﻿#include <iostream>

/**
 * 经典汉诺塔递归
 */
static void hanoiPrint(const int n, const char* from, const char* to, const char* transit)
{
    if (n == 1)
    {
        printf("第 %d 号盘从 %s 移动到 %s.\n", n, from, to);
        return;
    }

    // 将n-1从from移动到transit
    hanoiPrint(n - 1, from, transit, to);
    printf("第 %d 号盘从 %s 移动到 %s.\n", n, from, to);
    // 将n-1从transit移动到to
    hanoiPrint(n - 1, transit, to, from);
}

/**
 * @return 根据arr中的状态arr[0...i], 它是最优解的第几步? 
 */
static int process(const int* arr, const size_t arrSize, const int i, const int from, const int transit, const int to)
{
    // 没有圆盘了
    if (i == -1) return 0;

    if (arr[i] != from && arr[i] != to) return -1;

    if (arr[i] == from)
    {
        // 第1大步没有走完, 0~i-1 从from到transit
        return process(arr, arrSize, i - 1, from, to, transit);
    }
    else
    {
        // 第1大步和第2大步走完
        // 第3大步的完成情况
        int rest = process(arr, arrSize, i - 1, transit, from, to);
        if (rest == -1) return -1;

        return (1 << i) + rest;
    }
}

/**
 * 汉诺塔游戏的要求把所有的圆盘从左边都移动到右边的柱子上，给定一个整型数组arr，其中只含有1、2和3，代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，arr[i]的值代表第i+1个圆盘的位置。
 * 比如，arr=[3,3,2,1],代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。
 * 如果arr代表的状态是最优移动轨迹过程中出现的状态，返回arr这种状态是最优移动轨迹中的第几个状态；如果arr代表的状态不是最优移动轨迹过程中出现 状态，则返回-1.
 * 
 * 思路:
 * N层汉诺塔问题，最优解需要2^N-1步.
 * 假设第i层汉诺塔，拆分步骤为:
 * 1) 1~i-1从from移动到transit上去
 * 2) i从from移动到to上去
 * 3) 1~i-1从transit移动到to上去
 * 
 * 假如第i层圆盘的状态在from上，说明上面的步骤1)没结束; 假如第i层圆盘的状态在to上，说明上面的步骤1)和2)已经结束了, 这个时候的步数是2^(i-1)-1+1；假如第i层圆盘的状态在other上，则不是最优解的任何一步，返回-1
 */
int main_hanoiNthState()
{
    //hanoiPrint(4, "左柱", "右柱", "中柱");

    int arr[] = {3,3};
    auto arrSize = sizeof(arr) / sizeof(int);
    int nTh = process(arr, arrSize, 1, 1, 2, 3);
    printf("nTh=%d\n", nTh);

    return 0;
}